package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC685 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 图搜索，使用并查集，hard难度
     * @return:
     */
    public class Solution {

        public int[] findRedundantDirectedConnection(int[][] edges) {
            // 边的条数（在这个问题里等于结点个数）
            int len = edges.length;
            // 步骤 1：预处理入度数组（记录指向某个结点的边的条数）
            int[] inDegree = new int[len + 1];
            for (int[] edge : edges) {
                inDegree[edge[1]]++;
            }

            // 步骤 2：先尝试删除构成入度为 2 的边，看看是否形成环
            for (int i = len - 1; i >= 0; i--) {
                if (inDegree[edges[i][1]] == 2) {
                    // 如果不构成环，这条边就是要去掉的那条边
                    if (!judgeCircle(edges, len, i)) {
                        return edges[i];
                    }
                }
            }

            // 步骤 3：再尝试删除构成入度为 1 的边，看看是否形成环
            for (int i = len - 1; i >= 0; i--) {
                if (inDegree[edges[i][1]] == 1) {
                    // 如果不构成环，这条边就是要去掉的那条边
                    if (!judgeCircle(edges, len, i)) {
                        return edges[i];
                    }
                }
            }
            throw new IllegalArgumentException("输入不符合要求。");
        }

        /**
         * 将 removeEdgeIndex 去掉以后，剩下的有向边是否构成环
         *
         * @param edges
         * @param len             结点总数（从 1 开始，因此初始化的时候 + 1）
         * @param removeEdgeIndex 删除的边的下标
         * @return 构成环，返回 true
         */
        private boolean judgeCircle(int[][] edges, int len, int removeEdgeIndex) {
            UnionFind unionFind = new UnionFind(len + 1);
            for (int i = 0; i < len; i++) {
                if (i == removeEdgeIndex) {
                    continue;
                }
                if (!unionFind.union(edges[i][0], edges[i][1])) {
                    // 合并失败，表示 edges[i][0] 和 edges[i][1] 在一个连通分量里，即构成了环
                    return true;
                }
            }
            return false;
        }

        private class UnionFind {
            // 代表元法
            private int[] parent;

            public UnionFind(int n) {
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            public int find(int x) {
                while (x != parent[x]) {
                    // 路径压缩（隔代压缩）
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            /**
             * @param x
             * @param y
             * @return 如果合并成功返回 true
             */
            public boolean union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);

                if (rootX == rootY) {
                    return false;
                }
                parent[rootX] = rootY;
                return true;
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC685 an = new LC685();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
